package com.yun.datastructure.tree.binarytree.leetcode;

import com.yun.datastructure.tree.binarytree.domain.TreeNode;

public class Leetcode106 {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return split(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
    }

    private TreeNode split(int[] inorder, int[] postorder, int inH, int inT, int postH, int postT) {
        if (postT == postH) {
            return new TreeNode(postorder[postT]);
        }
        if (postT < postH) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postT]);
        int sp = 0;
        for (int i = inT; i >= inH; i--) {
            if (inorder[i] == postorder[postT]) {
                break;
            }
            sp++;
        }
        root.left = split(inorder, postorder, inH, inT - sp - 1, postH, postT - sp - 1);
        root.right = split(inorder, postorder, inT - sp, inT, postT - sp, postT - 1);
        return root;
    }
}
